Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule.
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/

Zadanie Robot (rob)

Robot

Limit pamięci: 64 MB

Jaś dostał na urodziny programowalnego robota. Robot ten potrafi zapamiętać sekwencję maksymalnie ruchów. Po uruchomieniu robot wykonuje kolejne ruchy sekwencji. Po wykonaniu wszystkich ruchów robot zaczyna wykonywać sekwencję od początku.

Rodzice Jasia wymyślili następującą zabawę. Umieszczają robota w lewym górnym rogu szachownicy. Następnie na niektórych pozostałych polach szachownicy umieszczają przeszkody, przez które nie może przejść robot. Zadaniem Jasia jest tak zaprogramować robota, aby ten wyszedł poza planszę. Dozwolone są dwa rodzaje ruchów - przejście robota o jedno pole w dół lub o jedno pole w prawo. Pomóż Jasiowi zaprogramować robota.

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite i (, ), gdzie to wymiar szachownicy. Kolejne linii zawiera ciągi znaków - opisy kolejnych wierszy szachownicy. Znak 'R' oznacza, że pole szachownicy zajmuje robot, '.' oznacza, że pole szachownicy jest wolne, natomiast 'X' oznacza pole zajęte. Możesz założyć, że robot zawsze będzie stał w lewym górnym rogu i istnieje sekwencja, która pozwala mu wyjść poza planszę.

Wyjście

Pierwszy i ostatni wiersz wyjścia zawiera ciąg co najwyżej znaków - opis sekwencji. Znak '1' oznacza ruch o jedno pole w dół, natomiast '0' przejście na pole po prawej stronie. Jeżeli istnieje więcej niż jedno rozwiązanie, to wypisz najkrótsze. Jeżeli istnieje więcej niż jedno najkrótsze rozwiązanie, to wypisz pierwsze w porządku leksykograficznym spośród najkrótszych.

Przykład

Dla danych wejściowych:

6 4
R.X...
X...XX
XXX...
X..XX.
XX.X.X
..X...

poprawną odpowiedzią jest:

Autor zadania: Mateusz Litwin (zapożyczenie).